NP 复杂度类

阐述

NP 是具有多项式验证者的语言集合。等价地，NP 是可以用一个非确定性 Turing 机在多项式时间内判定的问题的集合。

\mathrm{NP}=\bigcup_{k} \operatorname{NTIME}\left(n^{k}\right)

与 P 复杂度类一样，NP 对合乎情理的非确定性计算模型是不变的。

定义 coNP 是所有补集在 NP 中语言的集合。

称一个语言 $A$ 的验证者是 $V$ ，如果

A=\{w \mid V \text { accepts }\langle w, c\rangle \text { for some string } c\}

多项式时间验证者是能在 $|w|$ 的多项式时间内完成验证的验证者。显然，这要求其中的 $c$ ，也称凭证，的长度必须是多项式的。

称一个语言是多项式可验证的，如果它有一个多项式时间的验证者。